//后序遍历，方法一可以使用前序遍历的方法，最后再进行逆序
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* rt=root;
        stack<TreeNode*> S;
        vector<int> ans;
        while(rt||!S.empty())
        {
            while(rt)
            {
                ans.push_back(rt->val);
                S.push(rt->left);
                rt=rt->right;
            }
            rt=S.top();
            S.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};


//后序遍历，方法二，标记法
lass Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>ans;
        stack<TreeNode*> S;
        TreeNode* lastTreeNode=nullptr;//上次访问的最后一个节点
        TreeNode* rt=root;
        while(rt||!S.empty())
        {
            while(rt)
            {
                S.push(rt);
                rt=rt->left;
            }
            rt=S.top();
            if(!rt->right||rt->right==lastTreeNode)
            {
                ans.push_back(rt->val);
                lastTreeNode=rt;
                S.pop();
                rt=nullptr;
            }
            else
            {
                rt=rt->right;
            }
        }
return ans;
    }
};

//第三种方法，递归
class Solution {
public:
    vector<int> ans;
    void postorder(TreeNode* root)
    {
        if(root==nullptr) return;
        postorder(root->left);
        postorder(root->right);
        ans.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        postorder(root);
        return ans;
    }
};
